package pro.softzhang.algo.lc0;

import pro.softzhang.algo.flag.knowledge.KBackTracking;
import pro.softzhang.algo.flag.theme.TMathPermulation;

import java.util.*;
import java.util.stream.Collectors;

/**
 * 46. 全排列
 * https://leetcode.cn/problems/permutations/description/
 */
@KBackTracking
@TMathPermulation
public class LC46_Permulations {
    public static void main(String[] args) {

    }

    /**
     *
     */
    static
    class Solution {
        public List<List<Integer>> permute(int[] nums) {
            List<List<Integer>> r = new LinkedList<>();
            doPermute(nums, 0, r);
            return r;
        }

        private void doPermute(int[] nums, int i, List<List<Integer>> r) {
            if(i == nums.length) {
                List<Integer> p = new LinkedList<>();
                for (int num : nums) {
                    p.add(num);
                }
                r.add(p);
                return;
            }

            for (int j = i; j < nums.length; j++) {
                swap(nums, i, j);
                doPermute(nums, i + 1, r);
                swap(nums, i, j);
            }
        }

        private void swap(int[] nums, int i, int j) {
            if(i != j) {
                int t = nums[i];
                nums[i] = nums[j];
                nums[j] = t;
            }
        }
    }

    /**
     *
     */
    static
    class Solution1 {
        public List<List<Integer>> permute(int[] nums) {
            List<List<Integer>> answer = new LinkedList<>();

            dfs(nums, new ArrayList<>(), answer);

            return answer;
        }

        private void dfs(int[] nums, List<Integer> path, List<List<Integer>> ans) {
            if (path.size() == nums.length) {
                ans.add(new LinkedList<>(path));
                return;
            }

            for (int num : nums) {
                if (!path.contains(num)) {
                    path.add(num);
                    dfs(nums, path, ans);
                    path.remove(path.size() - 1);
                }
            }
        }
    }
}
